package uba.algo3.tp3.tsp;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashMap;

public class BusquedaTabuD
{

	private Grafo g;
	private Constructiva constructiva;
	int costoMin = Integer.MAX_VALUE;
	
	public Grafo getG()
	{
		return g;
	}

	public void setG(Grafo g)
	{
		this.g = g;
	}
	
	public BusquedaTabuD(Grafo g)
	{
        this.g = g;
	}
	
	public Solucion get2TSP(int t, int toleranciaOriginal, int iterD_param)
	{
		constructiva = new Constructiva(getG());
		Solucion mejorSol = constructiva.get2TSP(); //mejor solucion hasta el momento
		Solucion mejorSolGlobal = new Solucion(mejorSol);
		int tolerancia = toleranciaOriginal;
		ArrayList<Intercambio> listaTabu = new ArrayList<Intercambio>();
		LinkedHashMap<Pair, Memo> memos = new LinkedHashMap<Pair, Memo>(16,(float) 0.75,true);
		int iterD = iterD_param;
		
		while(iterD > -1)
		{
			do{
				ArrayList<Integer> vecina2, vecina1;
				int tamPart1 = mejorSol.getCiclo1().size();
				int tamPart2 = mejorSol.getCiclo2().size();
				int max, maxOriginal, costoVecina, temp;
				Solucion mejorVecina = null;
				Intercambio intercambio = null;
				costoMin = Integer.MAX_VALUE;
				
				if(tamPart1 < tamPart2)//Siempre vamos a tener la solucion mas grande en el ciclo1
				{
					max = tamPart2;
					maxOriginal = tamPart2;
					
					temp = tamPart1;
					tamPart1 = tamPart2;
					tamPart2 = temp;
					/* cambio el orden de los ciclos, esto es para que se prueben todas las combinaciones posibles
					 *  cuando intercambiamos nodos entre diferentes ciclos */
					mejorSol.cambiarCiclos();
				}
				else
				{
					max = tamPart1;
					maxOriginal = tamPart1;
				}
				
				for(int i = 0; i < listaTabu.size();i++)
				{
					Intercambio inter = listaTabu.get(i);
					inter.restarTiempo();
					if(inter.getTiempoExpiracion() == 0)
					{
						listaTabu.remove(i);
					}
				}//O(tiempoExpiracion)
				
				for(int k = 0; k < maxOriginal - 2;k++)
				{
					Pair p = new Pair(tamPart1, tamPart2);
					if(memos.get(p) == null)
					{
						memos.put(p,new Memo(p));
					}
					
					for(int i = 1; i < max; i++)
					{
						for(int j = 1; j < max; j++)
						{
							vecina1 = mejorSol.getCiclo1();
							vecina2 = mejorSol.getCiclo2();
							
							if(vecina1.size() < vecina2.size())
							{
								ArrayList<Integer> vecinaTemp = vecina1;
								vecina1 = vecina2;
								vecina2 = vecinaTemp;
								tamPart1 = vecina1.size();
								tamPart2 = vecina2.size();
							}
							
							if(i != j)
							{
								
									if(i < tamPart2 && j < tamPart2) //swapeo de los nodos del ciclo2
									{
										int ii = vecina2.get(i);
										int jj = vecina2.get(j);
										
										if( !listaTabu.contains(new Intercambio(ii,jj,t)) && !listaTabu.contains(new Intercambio(jj,ii,t)) )//O(tiempoExpiracion)
										{
											swap(vecina2,i,j);
											costoVecina = g.calcular_costo(vecina1) + g.calcular_costo(vecina2);
											
											//Si es mejor solucion, paro de buscar soluciones vecinas y cambio la mejor solucion
											if(costoVecina < costoMin)
											{
												mejorVecina = new Solucion((ArrayList<Integer>) vecina1.clone(),(ArrayList<Integer>) vecina2.clone(),costoVecina);
												intercambio = new Intercambio(ii,jj,t);
												costoMin = costoVecina;
											}
											
											swap(vecina2,j,i);
										}
	
									}
									
									if(i < tamPart1 && j < tamPart1) //swapeo de los nodos del ciclo1
									{
										int ii = vecina1.get(i);
										int jj = vecina1.get(j);
										
										if( !listaTabu.contains(new Intercambio(ii,jj,t)) && !listaTabu.contains(new Intercambio(jj,ii,t)) )//O(tiempoExpiracion)
										{
											swap(vecina1,i,j);
											costoVecina = g.calcular_costo(vecina2) + g.calcular_costo(vecina1);
											
											if(costoVecina < costoMin)
											{
												mejorVecina = new Solucion((ArrayList<Integer>) vecina1.clone(),(ArrayList<Integer>) vecina2.clone(),costoVecina);
												intercambio = new Intercambio(ii,jj,t);
												costoMin = costoVecina;
											}
											
											swap(vecina1,j,i);
										}
									}
							}
							
							if(j < tamPart1 && i < tamPart2)
							{
								int ii = vecina2.get(i);
								int jj = vecina1.get(j);
								
								if(!listaTabu.contains(new Intercambio(ii,jj,t)) && !listaTabu.contains(new Intercambio(jj,ii,t)))//O(tiempoExpiracion)
								{
									swap(vecina1,vecina2,i,j);
									costoVecina = g.calcular_costo(vecina1) + g.calcular_costo(vecina2);
									
									if(costoVecina < costoMin)
									{
										mejorVecina = new Solucion((ArrayList<Integer>) vecina1.clone(),(ArrayList<Integer>) vecina2.clone(),costoVecina);
										intercambio = new Intercambio(ii,jj,t);
										costoMin = costoVecina;
									}
		
									swap(vecina1,vecina2,i,j);
								}
							}
							
						}
						
					}
	
					ArrayList<Integer> ciclo1 = mejorSol.getCiclo1();
					ArrayList<Integer> ciclo2 = mejorSol.getCiclo2();
					Integer temp2 = ciclo1.get(1);//Elegimos el primero ya que despues hacemos todas los swapeos posibles
					ciclo1.remove(1);
					ciclo2.add(temp2);
					
					tamPart1 = ciclo1.size();
					tamPart2 = ciclo2.size();
				}//O(n * n * n * (n + tiempoExpiracion)) = O(n^4 + n^3 * tiempoExpiracion)
				
				guardarEnMemo(mejorVecina, memos);//O(n)
				
				if(mejorVecina.getCosto() < mejorSolGlobal.getCosto())
				{
					tolerancia = toleranciaOriginal;
					mejorSolGlobal = new Solucion(mejorVecina);
				}
				else
				{
					tolerancia--;
				}
				
				mejorSol = mejorVecina;
				listaTabu.add(intercambio);
				
			}while(tolerancia!=0);//O(tolerancia * (n^4 + n^3 * tiempoExpiracion + n)) = O(tolerancia * (n^4 + n^3 * tiempoExpiracion))
			
			iterD--;
			tolerancia = toleranciaOriginal;
			mejorSol = crearSolucionDiversificada(memos);//O(n^2)
		}//O(diversificaciones * (n^2 + tolerancia * (n^4 + n^3 * tiempoExpiracion) ) ) = O(diversificaciones * tolerancia * (n^4 + n^3 * tiempoExpiracion) )
		
		return mejorSolGlobal;	
		
	}
	
	

	
	private Solucion crearSolucionDiversificada(LinkedHashMap<Pair, Memo> memos)
	{
		Memo menosAccedido = null;
		int minAccesos = Integer.MAX_VALUE;
		
		for(Memo m : memos.values())//O(n) ya que depende de la cantidad de particiones
		{
			if(m.getVecesAccedido() < minAccesos)
			{
				minAccesos = m.getVecesAccedido();
				menosAccedido = m;
			}
		}
		
		Pair p = menosAccedido.tams;
		
		ArrayList<Integer> l1 = new ArrayList<Integer>();
		ArrayList<Integer> l2 = new ArrayList<Integer>();
		ArrayList<Integer> numsUsados = new ArrayList<Integer>();
		int orig = g.orig;
		
		l1.add(0, orig);
		l2.add(0, orig);
		numsUsados.add(orig);
		
		for(int indice = 1; indice < p.getTam1(); indice++)//O(n)
		{
			int menor = menosAccedido.buscarElMenorPosible(indice, numsUsados);//O(n)
			l1.add(indice, menor);
			numsUsados.add(menor);
		}//O(n^2)
		
		for(int indice = p.getTam1() + 1; indice < p.getTam2() + p.getTam1(); indice++)
		{
			int menor = menosAccedido.buscarElMenorPosible(indice, numsUsados);//O(n)
			l2.add(indice - p.getTam1(), menor);
			numsUsados.add(menor);
		}//O(n^2)

		int costo = g.calcular_costo(l1) + g.calcular_costo(l2);
		
		return new Solucion(l1,l2,costo);
	}
	
	private void guardarEnMemo(Solucion mejorVecina, HashMap<Pair, Memo> memos)
	{
		ArrayList<Integer> c1 = mejorVecina.getCiclo1();
		ArrayList<Integer> c2 = mejorVecina.getCiclo2();
		
		Pair p = new Pair(c1.size(),c2.size());
		
		Memo m = memos.get(p);
		
		if(m == null)
		{
			m = new Memo(p);
		}
		
		m.marcarNums(c1, c2);//O(n)
		memos.put(p, m);
	}

	private void swap(ArrayList<Integer> v1, ArrayList<Integer> v2,
			int i, int j)
	{
		Integer temp = v1.get(j);
        v1.set(j,v2.get(i));
        v2.set(i,temp);

	}
	
	private void swap(ArrayList<Integer> a, int i, int j){
		Integer temp = a.get(i);   
        a.set(i,a.get(j));
        a.set(j,temp);
	}
	
}
